[ZJOI2019]-开关

$方法一:生成函数$

“神仙题！”（平庸的 xml 发出惊叹）

生成函数怎么想到的啊？/yiw 但的确很符合，因为按键是有顺序的，而每个键按多少次概率也不同，适合用形式幂级数表示。

设 $P = \sum p$.

分开考虑每个键。考虑 $[x^k]F_i(x)$ 表示第 $i$ 个位置按了 $k$ 次的概率贡献。当然是 EGF 啦因为是有顺序的按。

$$F_i(x) = \sum\limits_{n \geq 0} [n\ mod\ 2 == s_i] \frac{ ( \frac{p_i}{P} ) ^n}{n!} x^n$$ $$F(x) = \prod F_i(x)$$

写成 OGF $f(x) = \sum_k (k! * [x^k]F(x)) * x^k$

$[x^k]G_i(x)$ 表示第 $i$ 个位置按了 $k$ 次，状态不变的概率。

然而只有 $F$ 能干啥呢？我们要求的是第一次到达目标状态，所以需要容斥。具体来说，设 $g(x)$ 表示 $k$ 次状态不变的 OGF，可按上述方法求出；设 $h(x)$ 为答案 OGF，则 $f(x) = g(x) \cdot h(x)$, 则 $h(x) = \frac{f(x)}{g(x)}$.

根据期望的定义，答案形如 $\sum_i if(i)$ 。啊这不就是 $h(1)$ 的导数嘛！$h’(1)$ 就是最终答案。

$$G_i(x) = \sum\limits_{n \geq 0} [n\ mod\ 2 == 0] \frac{( \frac{p_i}{P} )^n}{n!} x^n$$ $$G(x) = \prod G_i(x)$$

写成 OGF $g(x) = \sum_k (k! * [x^k]G(x)) * x^k$

写成封闭形式

$$F_i(x) = \frac{e^{\frac{p_i}{P}x} + (-1)^{s_i} e^{-\frac{p_i}{P}x}}{2}$$ $$F(x) = \prod \frac{e^{\frac{p_i}{P}x} + (-1)^{s_i} e^{-\frac{p_i}{P}x}}{2}$$ $$G_i(x) = \frac{e^{\frac{p_i}{P}x} + e^{-\frac{p_i}{P}x}}{2}$$ $$G(x) = \frac{e^{\frac{p_i}{P}x} + e^{-\frac{p_i}{P}x}}{2}$$

将 $F(x)$ 写成 $\sum c_i e^{\frac{i}{P}x}$ 的形式，则有

$$f(x) = \sum_k \left( k![x^k]F(x) \right) x^k$$ $$= \sum_k k^j}{j!} ) )x^k$$ $$= \sum_k ( k! \sum_i c_i \frac{(\frac{i}{P})^k}{k!} ) x^k = \sum_k (\sum_i c_i (\frac{i}{P})^k) x^k$$ $$= \sum_i c_i \sum_k (\frac{i}{P})^k x^k = \sum_i \frac{c_i}{1 - \frac{i}{P}x}$$

同理有 $g(x) = \sum_i \frac{d_i}{1 - \frac{i}{P}x}$。$c_i$, $d_i$ 可以简单 $O(nP)$ 背包得出！

补充求导加减乘除法法则：

$$(f(x) + g(x))' = f'(x) + g'(x)$$ $$(f(x) - g(x))' = f'(x) - g'(x)$$ $$(f(x) \cdot g(x))' = f'(x)g(x) + f(x)g'(x)$$ $$(\frac{f(x)}{g(x)})' = \frac{f'(x)g(x) - f(x)g'(x)}{g(x)^2}$$

所以要求 $h’(x)$，只要计算出 $f(1)$, $f’(1)$, $g(1)$, $g’(1)$.

然后又是常识问题：无知如我就想直接带 1 进去了，但这不行！！！因为 $i = P$ 项的存在，函数不收敛！！！

怎么办？乘上 $1 - x$

$$f(x) = c_P + \sum\limits_{i \neq P} \frac{c_i(1 - x)}{1 - \frac{i}{P}x}$$ $$f(1) = c_P$$ $$f'(x) = \sum\limits_i \frac{ -c_i(1 - \frac{i}{P}x) - (c_i - c_ix)(-\frac{i}{P}) }{(1 - \frac{i}{P}x)^2} = \sum\limits_i \frac{ (\frac{i}{P} - 1)c_i }{ (\frac{i}{P}x - 1)^2 }$$ $$f'(1) = \sum\limits_{i \neq P} \frac{c_i}{\frac{i}{P} - 1}$$

同理 $g(1) = d_P$, $g’(1) = \sum\limits_{i \neq P} \frac{d_i}{\frac{i}{P} - 1}$

$$h'(1) = \sum\limits_{i \neq P} \frac{c_id_P - c_Pd_i}{(i - 1)d_P^2}$$

神奇！

$Code$

从中获得的启示：

• 多考虑实际意义，例如本题中期望 -> 导数。
• 推柿子：面对多项式束手无策，不如把它变成封闭形式搞事情，多项式的加减乘除和数的加减乘除类似的，还可以求导、ln、exp，多好啊！
• 推柿子：把 $\prod_{i = l}^{r}$ 变成一个 $r - l + 1$ 次的多项式，就可以 $\sum$ 啦！$\sum$ 就能搞事情啦！

$方法二：异或卷积$

咕咕？（生成函数搞累了